package leetcode_jz_offer.day6_bin_tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * 使用层序遍历遍历二叉树打印
 * 这里需要用到队列结构（先进先出）：将元素不断加入队列中，先加入第一层元素，加完加入第二层...以此类推
 **/
public class Num32I_从上到下打印二叉树 {
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public int[] levelOrder(TreeNode root) {
      if(root==null){
        return new int[0];
      }
      Deque<TreeNode> queue=new ArrayDeque<>();
      ArrayList<Integer> list=new ArrayList<>();//存储队列中出来的元素
      queue.add(root);//根节点入队
      while (!queue.isEmpty()){
        TreeNode node=queue.poll();
        list.add(node.val);
        if(node.left!=null){
          queue.add(node.left);
        }
        if(node.right!=null){
          queue.add(node.right);
        }
        //保证了始终按层序顺序加入
      }
      //此时队列为空，元素遍历完毕存储在list中，向数组迁移
      int size=list.size();
      int[] array=new int[size];
      for (int i = 0; i < size; i++) {
        array[i]=list.get(i);
      }
      return array;
    }
}
